{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #High-Access Employees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findHighAccessEmployees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #高访问员工"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的二维字符串数组 <code>access_times</code> 。对于每个 <code>i</code>（<code>0 &lt;= i &lt;= n - 1</code> ），<code>access_times[i][0]</code> 表示某位员工的姓名，<code>access_times[i][1]</code> 表示该员工的访问时间。<code>access_times</code> 中的所有条目都发生在同一天内。</p>\n",
    "\n",
    "<p>访问时间用 <strong>四位</strong> 数字表示， 符合 <strong>24 小时制</strong> ，例如 <code>\"0800\"</code> 或 <code>\"2250\"</code> 。</p>\n",
    "\n",
    "<p>如果员工在 <strong>同一小时内</strong> 访问系统 <strong>三次或更多</strong> ，则称其为 <strong>高访问</strong> 员工。</p>\n",
    "\n",
    "<p>时间间隔正好相差一小时的时间 <strong>不</strong> 被视为同一小时内。例如，<code>\"0815\"</code> 和 <code>\"0915\"</code> 不属于同一小时内。</p>\n",
    "\n",
    "<p>一天开始和结束时的访问时间不被计算为同一小时内。例如，<code>\"0005\"</code> 和 <code>\"2350\"</code> 不属于同一小时内。</p>\n",
    "\n",
    "<p>以列表形式，按任意顺序，返回所有 <strong>高访问</strong> 员工的姓名。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>access_times = [[\"a\",\"0549\"],[\"b\",\"0457\"],[\"a\",\"0532\"],[\"a\",\"0621\"],[\"b\",\"0540\"]]\n",
    "<strong>输出：</strong>[\"a\"]\n",
    "<strong>解释：</strong>\"a\" 在时间段 [05:32, 06:31] 内有三条访问记录，时间分别为 05:32 、05:49 和 06:21 。\n",
    "但是 \"b\" 的访问记录只有两条。\n",
    "因此，答案是 [\"a\"] 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>access_times = [[\"d\",\"0002\"],[\"c\",\"0808\"],[\"c\",\"0829\"],[\"e\",\"0215\"],[\"d\",\"1508\"],[\"d\",\"1444\"],[\"d\",\"1410\"],[\"c\",\"0809\"]]\n",
    "<strong>输出：</strong>[\"c\",\"d\"]\n",
    "<strong>解释：</strong>\"c\" 在时间段 [08:08, 09:07] 内有三条访问记录，时间分别为 08:08 、08:09 和 08:29 。\n",
    "\"d\" 在时间段 [14:10, 15:09] 内有三条访问记录，时间分别为 14:10 、14:44 和 15:08 。\n",
    "然而，\"e\" 只有一条访问记录，因此不能包含在答案中，最终答案是 [\"c\",\"d\"] 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>access_times = [[\"cd\",\"1025\"],[\"ab\",\"1025\"],[\"cd\",\"1046\"],[\"cd\",\"1055\"],[\"ab\",\"1124\"],[\"ab\",\"1120\"]]\n",
    "<strong>输出：</strong>[\"ab\",\"cd\"]\n",
    "<strong>解释：</strong>\"ab\"在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、11:20 和 11:24 。\n",
    "\"cd\" 在时间段 [10:25, 11:24] 内有三条访问记录，时间分别为 10:25 、10:46 和 10:55 。\n",
    "因此，答案是 [\"ab\",\"cd\"] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= access_times.length &lt;= 100</code></li>\n",
    "\t<li><code>access_times[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= access_times[i][0].length &lt;= 10</code></li>\n",
    "\t<li><code>access_times[i][0]</code> 仅由小写英文字母组成。</li>\n",
    "\t<li><code>access_times[i][1].length == 4</code></li>\n",
    "\t<li><code>access_times[i][1]</code> 采用24小时制表示时间。</li>\n",
    "\t<li><code>access_times[i][1]</code> 仅由数字 <code>'0'</code> 到 <code>'9'</code> 组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [high-access-employees](https://leetcode.cn/problems/high-access-employees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [high-access-employees](https://leetcode.cn/problems/high-access-employees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\",\"0549\"],[\"b\",\"0457\"],[\"a\",\"0532\"],[\"a\",\"0621\"],[\"b\",\"0540\"]]', '[[\"d\",\"0002\"],[\"c\",\"0808\"],[\"c\",\"0829\"],[\"e\",\"0215\"],[\"d\",\"1508\"],[\"d\",\"1444\"],[\"d\",\"1410\"],[\"c\",\"0809\"]]', '[[\"cd\",\"1025\"],[\"ab\",\"1025\"],[\"cd\",\"1046\"],[\"cd\",\"1055\"],[\"ab\",\"1124\"],[\"ab\",\"1120\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:\n",
    "        hashmap = dict()\n",
    "        for employee, access_time in access_times:\n",
    "            if employee in hashmap.keys():\n",
    "                hashmap[employee].append(int(access_time))\n",
    "            else:\n",
    "                hashmap[employee] = [int(access_time)]\n",
    "        \n",
    "        ans = list()\n",
    "        for employee in hashmap.keys():\n",
    "            access_time = hashmap[employee]\n",
    "            if len(access_time)<3:\n",
    "                continue\n",
    "            access_time.sort()\n",
    "            for t in range(len(access_time)-2):\n",
    "                # 0215 0315\n",
    "                if access_time[t+2] < access_time[t]+100:\n",
    "                    ans.append(employee)\n",
    "                    break\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findHighAccessEmployees(self, arr: List[List[str]]) -> List[str]:\n",
    "        s=defaultdict(list)\n",
    "        for name,t in arr:\n",
    "            s[name].append(int(t[:2])*60+int(t[2:]))\n",
    "        ans=[]\n",
    "        for name,t in s.items():\n",
    "            t.sort()\n",
    "            if any(t[i]-t[i-2]<60 for i in range(2,len(t))):\n",
    "                ans.append(name)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:\n",
    "        test = defaultdict(list)\n",
    "        for i, j in access_times:\n",
    "            test[i].append(j)\n",
    "        ans = []\n",
    "        for i in test:\n",
    "            if len(test[i]) >= 3:\n",
    "                test[i].sort()\n",
    "                for j in range(2, len(test[i])):\n",
    "                    x, y = test[i][j - 2], test[i][j]\n",
    "                    a = int(x[:2]) * 60 + int(x[2:])\n",
    "                    b = int(y[:2]) * 60 + int(y[2:])\n",
    "                    if b - a < 60:\n",
    "                        ans.append(i)\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:\n",
    "        ans=[]\n",
    "        mp=defaultdict(list)\n",
    "        for a,b in access_times:\n",
    "            t=int(b[:2])*60+int(b[2:])\n",
    "            mp[a].append(t)\n",
    "        for x in mp:\n",
    "            mp[x].sort()\n",
    "            t=deque()\n",
    "            for a in mp[x]:\n",
    "                while t and a-t[0]>=60:\n",
    "                    t.popleft()\n",
    "                t.append(a)\n",
    "                if len(t)==3:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
